Measuring the effects of preprocessing decisions and network forces in dynamic network analysis

ABSTRACT

Social networks have become a major focus of research in recent years, initially directed towards static networks but increasingly, towards dynamic ones. In this paper, we investigate how different pre-processing decisions and different network forces such as selection and influence affect the modeling of dynamic networks. We also present empirical justification for some of the modeling assumptions made in dynamic network analysis (e.g., first-order Markovian assumption) and develop metrics to measure the alignment between links and attributes under different strategies of using the historical network data. We also demonstrate the effect of attribute drift, that is, the importance of individual attributes in forming links change over time.

REFERENCES

• 1: Edoardo M. Airoldi , Kathleen M. Carley, Sampling algorithms for pure network topologies: a study on the stability and the separability of metric embeddings, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.13-22, December 2005 [doi>10.1145/1117454.1117457]
• 2: Aris Anagnostopoulos , Ravi Kumar , Mohammad Mahdian, Influence and correlation in social networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401897]
• 3: A.-L. Barabasi and E. Bonabeau. Scale-free networks. Scientific American, 288:50--59, May 2003.
• 4: S. P. Borgatti and M. G. Everett. Models of core / periphery structures. Social Networks, 21:375--395, 1999.
• 5: David Crandall , Dan Cosley , Daniel Huttenlocher , Jon Kleinberg , Siddharth Suri, Feedback effects between similarity and social influence in online communities, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401914]
• 6: P. ErdÄos and A. Renyi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5:17--61, 1960.
• 7: T. Frantz and K. M. Carley. A formal characterization of cellular networks. Technical Report CMU-ISRI-05-109, Carnegie Mellon University, 2005.
• 8: C. Guestrin, D. Koller, C. Gearhart, and Neal Kanodia. Generalizing plans to new environments in relational mdps. In International Joint Conference on Artificial Intelligence, 2003.
• 9: S. Hanneke and E. Xing. Discrete temporal models of social networks. In Proceedings of the 23rd International Conference on Machine Learning Workshop on Statistical Network Analysis, 2006.
• 10: M. Al Hasan, V. Chaoji, S. Salem, and M. Zaki. Link prediction using supervised learning. In Proceedings of SDM'06: SIAM Data Mining Conference Workshop on Link Analysis, Counter-terrorism and Security, 2006.
• 11: Kansas event data system. http://web.ku.edu/keds.
• 12: David Kempe , Jon Kleinberg , Amit Kumar, Connectivity and inference problems for temporal networks, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.504-513, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335364]
• 13: M. Lahiri and T. Y. Berger-Wolf. Structure prediction in temporal networks using frequent subgraphs. In IEEE Symposium on Computational Intelligence and Data Mining (CIDM), 2007.
• 14: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 15: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 16: J. McPherson, L. Smith-Lovin, and J. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27:415--444, 2001.
• 17: Jennifer Neville , David Jensen, Leveraging Relational Autocorrelation with Latent Group Models, Proceedings of the Fifth IEEE International Conference on Data Mining, p.322-329, November 27-30, 2005 [doi>10.1109/ICDM.2005.89]
• 18: Joshua O'Madadhain , Jon Hutchins , Padhraic Smyth, Prediction and ranking algorithms for event-based network data, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.23-30, December 2005 [doi>10.1145/1117454.1117458]
• 19: M. Pearson, C. Steglich, and T. Snijders. Homophily and assimilation among sport-active adolescent substance users. Connections, 27:47--63, 2006.
• 20: A. Popescul and L. H. Ungar. Statistical relational learning for link prediction. In Proceedings of the IJCAI Workshop on Learning Statistical Models from Relational Data, 2003.
• 21: Matthew J. Rattigan , David Jensen, The case for anomalous link discovery, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.41-47, December 2005 [doi>10.1145/1117454.1117460]
• 22: J. Scripps, P. N. Tan, and A-H Esfahanian. A matrix alignment approach for link prediction. In Proceedings of the Nineteenth international conference on pattern recognition, 2008.
• 23: Umang Sharan , Jennifer Neville, Temporal-Relational Classifiers for Prediction in Evolving Domains, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.540-549, December 15-19, 2008 [doi>10.1109/ICDM.2008.125]
• 24: T. Snijders. Models for longitudinal network data. In P. Carrinton, J. Scott, and S. Wasserman, editors, Models and methods in social network analysis. Cambridge University Press, 2004.
• 25: B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI02), 2002.
• 26: B. Taskar, M. F. Wong, P. Abbeel, and D. Koller. Link prediction in relational data. In Neural Information Processing Systems Conference (NIPS03), 2003.
• 27: Siena network statistical analysis program. http://stat.gamma.rug.nl/snijders/siena.html.
• 28: S. Wasserman and P. Pattison. Logit models and logistic regression for social networks: I an introduction to markov graphs and p*. Psychometrika, 61:401--425, 1996.
• 29: D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature, pages 440--442, Jun 1998.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Measurement

Keywords:
data mining, dynamic networks, networks